package com.zhugang.week12;

import java.util.Arrays;

/**
 * @program algorithms
 * @description: twoSum
 * @author: chanzhugang
 * @create: 2022/09/06 18:50
 */
public class TwoSum {

    /**
     * 1 两数之和
     * 双指针解法
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        // 双指针试试：i、j, 排序后下标乱了，所以构建一个新的排序数组
        int n = nums.length;
        int[] sortedNums = new int[n];
        for (int i = 0; i < n; i++) {
            sortedNums[i] = nums[i];
        }
        // 新的排序数组
        Arrays.sort(sortedNums);
        boolean[] used = new boolean[n];
        int i = 0;
        int j = n - 1;
        while (i < j) {
            if (sortedNums[i] + sortedNums[j] == target) {
                // 找值在原数组中的下标
                int oldi = find(nums, used, sortedNums[i]);
                int oldj = find(nums, used, sortedNums[j]);
                return new int[]{oldi, oldj};
            } else if (sortedNums[i] + sortedNums[j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return new int[]{};
    }

    /**
     * 给定值在原数组中的位置
     *
     * @param nums
     * @param used
     * @param value
     * @return
     */
    private int find(int[] nums, boolean[] used, int value) {
        int i = 0;
        while (i < nums.length) {
            if (nums[i] == value && !used[i]) {
                used[i] = true;
                break;
            }
            i++;
        }
        return i;
    }
}